/*
560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。


示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2
 

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
*/

/*
使用了前缀和

根据

S(i, j) = S(j + 1) - S(i)

即 求 i 到 j 之间的和可以使用 0 到 j 之间的和减去 0 到 i 之间的和

！为什么要使用 S(j + 1) - S(i) 而不是像数学中一样 S(j) - S(i - 1) 呢？
根本原因是因为，数学中是从 1 开始的，所以数学中的下标 1 就是前缀和的第一项
而编程中是从 0 开始的，所以编程中的下标 1 是从 0 开始的，所以在编程中 j + 1 就是前缀和从 0 到 j 的和，i 就是前缀和从 0 到 i - 1 的和
*/
class Solution {
    public int subarraySum(int[] nums, int k) {
        // 计数器：记录和为k的子数组个数
        int count = 0;

        // 当前前缀和：从数组开始到当前位置的所有元素之和
        int currentSum = 0;

        // 哈希表：记录每个前缀和值出现的次数
        // key: 前缀和的值
        // value: 该前缀和值出现的次数
        Map<Integer, Integer> prefixSumCount = new HashMap<>();

        /**
         * 🎯 关键初始化：为什么需要 put(0, 1)？
         *
         * 考虑从数组第一个元素开始的子数组：
         * 比如 nums = [2], k = 2
         * 当遍历到第一个元素时：currentSum = 2
         * 我们需要找 currentSum - k = 2 - 2 = 0
         * 如果没有这个初始值，就找不到这个子数组
         *
         * 物理意义：空数组的前缀和为0，出现1次
         */
        prefixSumCount.put(0, 1);

        /**
         * 遍历数组中的每个元素
         * 对于每个位置，我们计算以该位置结尾的和为k的子数组个数
         */
        for (int num : nums) {
            // 更新当前前缀和：加上当前元素的值
            currentSum += num;

            /**
             * 🧠 核心逻辑：查找是否存在满足条件的前缀和
             *
             * 我们要找的是：子数组 [i..j] 的和 = k
             * 根据前缀和性质：currentSum - prefix[i] = k
             * 移项得：prefix[i] = currentSum - k
             *
             * 所以问题转化为：前面有多少个位置i，使得 prefix[i] = currentSum - k
             * 每个这样的位置i，都对应一个以当前位置j结尾的和为k的子数组
             */
            if (prefixSumCount.containsKey(currentSum - k)) {
                // 如果存在，说明找到了若干个以当前位置结尾的和为k的子数组
                // 个数等于 currentSum - k 这个前缀和值出现的次数
                count += prefixSumCount.get(currentSum - k);
            }

            /**
             * 📊 更新哈希表：记录当前前缀和的出现次数
             *
             * getOrDefault 方法：
             * - 如果 currentSum 已经在map中，返回对应的值
             * - 如果不在，返回默认值0
             * 然后加1，表示当前前缀和又多出现了一次
             */
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }
}